#ifndef __BINNODE_H
#define __BINNODE_H 

#include <cstdio>
#define IsRoot(x) (!((x).parent))
#define IsLChild(x) (!IsRoot(x) && (& (x) == (x).parent->lc))
#define IsRChild(x) (!IsRoot(x) && (& (x) == (x).parent->rc))
#define HasParent(x) (!IsRoot(x))
#define HasLChild(x) ((x).lc)
#define HasRChild(x) ((x).rc)
#define HasChild(x) (HasLChild(x) || HasRChild(x))

template <typename T> void visit(T const&);

template <typename T> class BinNode{
public:
	T data;
	int height;
	BinNode<T>* parent;
	BinNode<T>* lc;
	BinNode<T>* rc;

	BinNode():parent(NULL),lc(NULL),rc(NULL),height(0){}
	BinNode(T e,BinNode<T>* p = NULL,BinNode<T>* l = NULL,BinNode<T>* r = NULL,
			int h = 0):data(e),parent(p),lc(l),rc(r),height(h){}

	BinNode<T>* insertAsLC(T const&);
	BinNode<T>* insertAsRC(T const&);
	BinNode<T>* succ();
//遍历接口
	template <typename VST> void travLevel(VST &visit);		//广度优先遍历
};

template <typename T> int stature(BinNode<T> *x);
#endif
